[WIP] 74. Search a 2D Matrix

Question

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints: m == matrix.length n == matrix[i].length 1 <= m, n <= 100 -104 <= matrix[i][j], target <= 104

---

Approach

Solution

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = 0;
        if(matrix.size() == 1 && matrix[0].size() == 1){
            if(matrix[0][0] != target) return false;
            return true;
        }
        
        //find row
        for(int i = 0; i < matrix.size(); i++){
            if(target < matrix[i][0]){
                if(i == 0) row = 0; 
                else row = i - 1;
                break; 
            }else if(target == matrix[i][0]){
                row = i;
                break;
            }
            
            //last row, and target is > than first element
            if(i == matrix.size() - 1){
                if(target > matrix[i][0]){
                    row = i;
                    break;
                }
            }
        }
        
        for(int j = 0; j < matrix[row].size(); j++){
            if(matrix[row][j] == target) return true;
        }
        
        return false;
    }
};